import std/algorithm
import std/sugar

type
  Specimen = concept x, y, type T
    T.initSpecimen is T
    cmpFitness(x, y) is int
    x.mutated is T

proc maximizeFitness*[S: Specimen](
    numGenerations: Positive = 1000,
    constantReproductionCoefficient: Positive = 20,
    linearReproductionCoefficient: Natural = 1,
    reproductionCap: Positive = 1000,
    postGeneration = (proc(generation: Natural, pool: seq[S]) = discard),
  ): S =
  mixin cmpFitness
  let reproductionNumber = if linearReproductionCoefficient == 0:
    reproductionCap
  else:
    min(reproductionCap, (constantReproductionCoefficient - 1) div linearReproductionCoefficient + 1)
  let poolSize = reproductionNumber * (constantReproductionCoefficient + 1) -
                 linearReproductionCoefficient * (linearReproductionCoefficient - 1) div 2
  var pool = newSeq[Specimen](poolSize)
  for specimen in pool.mitems:
    specimen = S.initSpecimen()
  for generation in 0..<numGenerations:
    pool.sort(cmpFitness)
    postGeneration(generation, pool)
    var childIndex = reproductionNumber
    for parentIndex, parent in pool[0..<reproductionNumber]:
      for _ in 0..<(constantReproductionCoefficient - parentIndex * linearReproductionCoefficient):
        pool[childIndex] = parent.mutated
  pool[0]
